package leetcode.editor.cn.dsa12_divideAndConquer;
//给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。
//
// 示例: 
// 现有矩阵 matrix 如下：
// [
//  [1,   4,  7, 11, 15],
//  [2,   5,  8, 12, 19],
//  [3,   6,  9, 16, 22],
//  [10, 13, 14, 17, 24],
//  [18, 21, 23, 26, 30]
//]
//
// 给定 target = 5，返回 true。 
// 给定 target = 20，返回 false。
//
// Related Topics 双指针 二分查找 分治算法 
// 👍 15 👎 0

public class SortedMatrixSearchLcci1009 {
    public static void main(String[] args) {
        Solution solution = new SortedMatrixSearchLcci1009().new Solution();
        int[][] matrix = {
                {1,   4,  7, 11, 15},
                {2,   5,  8, 12, 19},
                {3,   6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        System.out.println(solution.searchMatrix(matrix, 5)); //true
        System.out.println(solution.searchMatrix(matrix, 20)); //false
        System.out.println(solution.searchMatrix(matrix, 30)); //true
        System.out.println(solution.searchMatrix(matrix, 100)); //false
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length; if(m == 0) return false; // 行数
            int n = matrix[0].length; if(n == 0) return false; // 列数
            // 使用分治思想查找元素
            // 矩阵区域需要左上角下标（行、列）、右下角下标（行、列）
            return searchSubMatrix(matrix, target, 0, 0, m - 1, n - 1);
        }

        /**
         * startRow、startColumn表示矩阵左上顶点的坐标
         * endRow、endColumn表示矩阵右下顶点的坐标
         */
        public boolean searchSubMatrix(int[][] matrix, int target, int startRow,
                                       int startColumn, int endRow, int endColumn) {
            // 结束条件：元素个数小于1(超出矩阵范围)或者矩阵最小元素大于目标值
            if (startRow > endRow || startColumn > endColumn) return false;
            System.out.println("查找的子矩阵：" + matrix[startRow][startColumn] + "," + matrix[endRow][endColumn]);
            if(matrix[startRow][startColumn] > target) return false;
            // 函数主功能：在对角线上查找元素、分解问题、递归求解、合并
            // 求对角线元素个数，细节问题：矩阵行、列可能不相等
            int diagonalLen = Math.min(endRow - startRow + 1, endColumn - startColumn + 1);
            for (int i = 0; i < diagonalLen; i++) {
                // 在对角线上找到则返回true
                if (matrix[startRow + i][startColumn + i] == target) return true;
                // 如果到达对角线上最后一个元素或者元素大于目标值，则进行分解--递归求解--合并
                if (i == diagonalLen - 1 || matrix[startRow + i + 1][startColumn + i + 1] > target) {
                    // 找到了分界点，寻找4个区域中剩下的两个 （右上、左下）
                    //等价关系式：f(m)=f(m1)||f(m2)，m1、m2为划分后待查找的子矩阵
                    return searchSubMatrix(matrix, target, startRow, startColumn + i + 1, startRow + i, endColumn)
                            || searchSubMatrix(matrix, target, startRow + i + 1, startColumn, endRow, startColumn + i);
                }
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}